package cn.walls1717.leetcode.array;

/**
 * 367. 有效的完全平方数
 * 力扣地址：https://leetcode-cn.com/problems/valid-perfect-square/
 *
 * @author walls1717
 * @since 2022-04-30
 **/
public class T367 {

    public static void main(String[] args) {
        System.out.println(isPerfectSquare(2147483647));
    }

    public static boolean isPerfectSquare(int num) {
        // 特殊情况，0和1都是完全平方数
        if (num == 0 || num == 1) {
            return true;
        }
        int l = 0;
        int r = num;
        int mid;
        while (l <= r) {
            mid = l + ((r - l) >> 1);
            // (long)是为了防止整数溢出，如果中间值的平方等于这个整数
            // 那么说明这个数是有效完全平方数
            if ((long)mid * mid == num) {
                return true;
            } else if ((long)mid * mid < num) {
                // 中间值平方小于这个整数
                // 那么左边找
                l = mid + 1;
            } else {
                r = mid - 1;
            }
        }
        return false;
    }
}
